/* 动态中位数 
维护两个堆
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
    // freopen("1.in","r",stdin);
    int n;
    scanf("%d",&n);
    priority_queue<int> l,r;
    int a;
    scanf("%d",&a);
    l.push(a);
    printf("%d\n",a);
    for(int i=2;i<=n;i++){
        scanf("%d",&a);
        if(a>l.top())r.push(-a);
        else l.push(a);
        if(l.size()>r.size()+1)r.push(-l.top()),l.pop();
        if(r.size()>l.size())l.push(-r.top()),r.pop();
        if(i&1)printf("%d\n",l.top());
    }
}